//
//  36.两个链表的第一个公共节点.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/24.
//

import Foundation
/*
 题目：输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
  
 思路1：我们可以把两个链表拼接起来，⼀个pHead1在前pHead2在后，⼀个pHead2在前pHead1在后。这样，⽣成了两个相同⻓度的链表，那么我们只要同时 遍历这两个表，就⼀定能找到公共结点。时间复杂度O(m+n)，空间复杂度O(m+n)。
 */
func offer_36() {
    let node1 = Solution.ListNode(val: 1)
    let node2 = Solution.ListNode(val: 2)
    let node3 = Solution.ListNode(val: 3)
    let node4 = Solution.ListNode(val: 4)
    let node5 = Solution.ListNode(val: 5)
    let node6 = Solution.ListNode(val: 6)
    let node7 = Solution.ListNode(val: 7)
    let node8 = Solution.ListNode(val: 8)
    node1.next = node3
    node3.next = node5
    node2.next = node4
    node4.next = node6
    node7.next = node8
    node5.next = node7
    node6.next = node7
    
    print(Solution().findFirstCommonNode(node1, node2)?.val ?? "nil")
}

fileprivate class Solution {
    class ListNode {
        var val: Int
        var next: ListNode?
        init(val: Int) {
            self.val = val
        }
    }
    
    func findFirstCommonNode(_ pHead1: ListNode?, _ pHead2: ListNode?) -> ListNode? {
        var p1 = pHead1, p2 = pHead2
        while p1 !== p2 {
            p1 = p1?.next != nil ? p1?.next : pHead2
            p2 = p2?.next != nil ? p2?.next : pHead1
        }
        return p1
    }
}


